package Hot100.DP;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

public class canPartition {
    public static void main(String[] args) {
        int[] nums = {1,2,3,5};
        System.out.println(new canPartition().canPartition(nums));
    }
    public boolean canPartition(int[] nums) {
        int all = 0;

        for (int i = 0; i < nums.length; i++) {
            all += nums[i];
        }
        if(all % 2 != 0){
            return false;
        }
        int target = all / 2;
        int[] dp = new int[target + 1];
        for(int i = 0; i < nums.length; i++) { // 遍历物品
            for(int j = target; j >= nums[i]; j--) { // 遍历背包容量
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        if(dp[target] == target){
            return true;
        }
        return false;
    }
}
